# 岛屿数量


class Solution:

    def numIslands(self, grid: list[list[str]]) -> int:

        def dfs(grid, i, j):
            if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or grid[i][j] == '0':
                return
            
            grid[i][j] = '0'

            dfs(grid, i+1, j)
            dfs(grid, i-1, j)
            dfs(grid, i, j+1)
            dfs(grid, i, j-1)
            

        count = 0

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                # 发现陆地时，将陆地周围的1都归一为0，避免重复搜索
                if grid[i][j] == '1':

                    dfs(grid, i, j)

                    count += 1

        return count




if __name__ == "__main__":

    a = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]

    sol = Solution()
    count = sol.numIslands(a)
    print(count)